package pro.softzhang.algo.lc900;

import pro.softzhang.algo.flag.book.BDaily;
import pro.softzhang.algo.flag.difficulty.DRed;

@BDaily
@DRed
public class LC940_DistinctSubsequencesII {
    public static void main(String[] args) {

    }

    static class Solution {
        public int distinctSubseqII(String s) {
            int mod = (int)1e9 + 7, dc = 0;
            int[] dp = new int[26];
            for (int i = 0; i < s.length(); i++) {
                int ch = s.charAt(i) - 'a', prev = dp[ch];
                dp[ch] = (dc + 1) % mod;
                dc = (dc + dp[ch]) % mod;
                dc = (dc - prev + mod) % mod;
            }
            return dc;
        }
    }
}
